package leetcode_周赛._2023._03;

import java.util.HashMap;
import java.util.Map;

/**
 * 335 场周赛
 * AC 2
 *
 * @author yezh
 * @date 2023/3/5 19:50
 */
public class _05 {

    /**
     * 递枕头
     * 算法: 数学
     * t = time / (n - 1) 下取整
     * t 为 偶数, 0 - n
     * t 为 奇数, n - 0
     */
    public int passThePillow(int n, int time) {
        int cur = time % (n - 1);
        if (time / (n - 1) % 2 == 0) return cur + 1;
        else return n - cur;
    }

    /**
     * 分割数组使乘积互质
     * 算法: 数学
     * 算出每个 nums 中的所有质数,
     * 针对每个 i, 找到和它拥有相同质数的最远距离 d
     * 这样就形成了 [i, d] 的区间
     * 1、算质数
     * 2、找分割点
     */
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> left = new HashMap<>();
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int d = 2; d * d <= x; d++) {
                if (x % d == 0) {
                    // 记录左端点对应的右端点的最大值
                    if (left.containsKey(d)) right[left.get(d)] = i;
                        // 第一次遇到质数 d
                    else left.put(d, i);
                    for (x /= d; x % d == 0; x /= d) ;
                }
            }
            if (x > 1) {
                if (left.containsKey(x)) right[left.get(x)] = i;
                else left.put(x, i);
            }
        }
        for (int l = 0, maxR = 0; l < n; l++) {
            if (l > maxR) return l - 1;
            maxR = Math.max(maxR, right[l]);
        }
        return -1;
    }

}
